// https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

// 算法思路总结：
// 1. 栈思想处理相邻重复字符删除问题
// 2. 遍历字符串，用结果字符串模拟栈行为
// 3. 当前字符与栈顶相同则弹出，否则压入
// 4. 利用字符串的back()和pop_back()操作
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    string removeDuplicates(string s) 
    {
        int m = s.size();
        string res;

        for (const char& ch : s)
        {
            if (res.empty())
                res.push_back(ch);
            else if (res.back() != ch)
                res.push_back(ch);
            else
                res.pop_back();
        }
        return res;
    }
};

int main()
{
    string s = "abbaca";
    Solution sol;

    cout << sol.removeDuplicates(s) << endl;

    return 0;
}